/**
 * 
 */
package truerefactor.genetic;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;

import truerefactor.RefactoringController;
import truerefactor.codesmell.CodeSmell;
import truerefactor.graph.CodeGraph;
import truerefactor.graph.GraphPool;
import truerefactor.metrics.Metric;
import truerefactor.refactor.Refactoring;

/**
 * GeneticAlgorithm - This object represents the brain of the system. It uses a
 * GA to control the refactoring and code smell removal for the system by using
 * a GA form of state space search. This works by taking a given list of
 * possible and correct refactoring sequences (generated by the code smell
 * classes) and randomly selecting from the list to generate a set of possible
 * solutions. It then continuously modifies these solutions or generates new
 * ones in order to find the best possible solution (which decreases both the
 * measured fitness (product metrics) and code smell (after application of the
 * refactorings)) within a certain amount of iterations.
 * 
 * @author Isaac Griffith
 * @author Scott Wahl
 */
public class GeneticAlgorithm implements Runnable {

    /**
     * Refactoring Controller to which this GA is associated
     */
    private RefactoringController controller;
    /**
     * The initial measurement of Total Code Smell count
     */
    private double initialSmell;
    /**
     * The GASmell container for individual initial smell counts
     */
    private GASmell initialSmells;
    /**
     * The initial measurement container of individual Fitness values
     */
    private Fitness initialVals;
    /**
     * The initial measurement of Total Fitness
     */
    private double initialVal = 0;
    /**
     * The Object containing the parameters for this GA
     */
    private GAParameters parameters;
    /**
     * The master list of refactoring sequences to be used to create individuals
     */
    private List<List<Refactoring>> sequences;

    /**
     * Creates a new GA associated with the given RefactoringController, using
     * the provided parameters and which builds its population with the provided
     * refactoring sequences.
     * 
     * @param controller
     *            Associated refactoring controller
     * @param parameters
     *            Genetic Algorithm Parameters used to set up and control this
     *            GA
     * @param sequences
     *            List of Refatoring sequences used to build the population
     */
    public GeneticAlgorithm(RefactoringController controller, GAParameters parameters, List<List<Refactoring>> sequences)
    {
        this.controller = controller;
        this.parameters = parameters;
        this.sequences = sequences;

        // if (parameters.getIndMaxSize() > sequences.size())
        // parameters.setIndMaxSize(sequences.size());

        initialVals = new Fitness(controller.getAvailableMetrics().size());
        initialSmells = new GASmell(controller.getAvailableCodeSmells().size());

        // maxFitnessSize = controller.getAvailableMetrics().size();

        calcInitialMeasurements();
    }

    /**
     * Calculates and records initial code smell and fitness measurements prior
     * to running the GA
     */
    private void calcInitialMeasurements()
    {
        controller.recordHeading(-1, "Initial Values Measurements");
        displayFitnessHeader(-1);
        calcFitness(-1, GraphPool.getInstance().acquireCodeGraph(), null);
        initialSmell = calcSmell(GraphPool.getInstance().acquireCodeGraph(), -1, null);

        controller.recordSmellLog(-1, initialSmell, initialSmells.getIndividualVals());
        controller.recordFitnessLog(-1, initialVal, initialVals.getIndividualVals());
    }

    /**
     * @return A newly constructed allele for use within an individual
     */
    private Allele newAllele(List<List<Refactoring>> availableSequences)
    {
        int index = (int) (Math.random() * availableSequences.size());

        return new Allele(availableSequences.remove(index));
    }

    /**
     * @return constructs a new Individual for use as a member of a population
     */
    private Individual newIndividual()
    {
        List<List<Refactoring>> availableSequences = new ArrayList<List<Refactoring>>();
        availableSequences.addAll(sequences);
        Collections.shuffle(availableSequences);
        Individual ind = new Individual(parameters.getMaxFitnessSize(), controller.getAvailableCodeSmells().size());

        int size = (int) (sequences.size() * parameters.getSmellFactor());

        for (int i = 0; i < size && !availableSequences.isEmpty(); i++)
            ind.addAllele(newAllele(availableSequences));

        return ind;
    }

    /**
     * Given the existing population from the previous generation. This
     * algorithm eliminates solutions through thresholding.
     * 
     * @param generation
     *            current generation of the GA
     * @param newGeneration
     *            list to be populated with the next generation of individuals
     * @param population
     *            the last generation's population of individuals
     */
    private void retainPopulation(int generation, List<Individual> population, List<Individual> newGeneration)
    {
        Iterator<Individual> indIter = newGeneration.listIterator();
        while (indIter.hasNext())
        {
            Individual ind = indIter.next();

            if (ind.getTotalFitness() > initialVal)
            {
                indIter.remove();
            }
        }

        // find the worst performers
        List<Double> totalVals = new ArrayList<Double>();
        for (Individual ind : population)
        {
            totalVals.add(ind.getTotalFitness() + ind.getTotalSmell());
        }

        for (int i = 0; i < newGeneration.size(); i++)
        {
            int index = totalVals.indexOf(Collections.max(totalVals));
            if (index >= 0)
            {
                population.remove(index);
                population.add(newGeneration.get(i));
            }
        }
    }

    /**
     * Given the list of parents this method creates a new list of individuals
     * representing the children of the previous generation. This method can be
     * used to generate a new generation of individuals to be used to continue
     * the genetic algorithm.
     * 
     * @param parents
     *            The previous generation's population of individuals.
     * @return the next generations list of individuals to replace portions of
     *         the previous generation.
     */
    private List<Individual> createChildren(List<Individual> parents)
    {
        int popSize = parents.size();
        double[] normSelection = new double[popSize];

        List<Individual> nextGeneration = new LinkedList<Individual>();

        // Create a list of normalized fitness values
        for (int i = 0; i < normSelection.length; i++)
        {
            double addVal = parents.get(i).getTotalFitness();
            normSelection[i] = (i == 0 ? 0 : normSelection[i - 1]) + addVal;
        }

        for (int i = 0; i < normSelection.length; i++)
            normSelection[i] /= normSelection[normSelection.length - 1];

        for (int i = 0; i < popSize / 2; i++)
        {
            List<Individual> newChildren = selectAndCrossover(normSelection, parents);

            Iterator<Individual> iter = newChildren.listIterator();
            while (iter.hasNext())
            {
                Individual ind = iter.next();
                if (ind.getSize() == 0)
                    iter.remove();
            }

            if (newChildren.isEmpty())
                continue;

            mutate(newChildren);

            // add the new children to the population
            nextGeneration.addAll(newChildren);
        }

        return nextGeneration;
    }

    /**
     * Selects parents and then crosses them over to generate children
     * 
     * @param normSelection
     *            The Normalized Fitness values
     * @param parents
     *            List of potential parent Individuals
     */
    private List<Individual> selectAndCrossover(double normSelection[], List<Individual> parents)
    {
        double pOneSelVal = Math.random();
        double pTwoSelVal = Math.random();

        Individual pOne = null;
        Individual pTwo = null;
        for (int j = 0; j < normSelection.length; j++)
        {
            if (pOneSelVal < normSelection[j])
            {
                pOne = parents.get(j);
                break;
            }
        }

        for (int j = 0; j < normSelection.length; j++)
        {
            if (pTwoSelVal < normSelection[j])
            {
                pTwo = parents.get(j);
                break;
            }
        }

        // crossover of the selected parents
        return pOne.crossover(pTwo);
    }

    /**
     * For each child individual passed in the given list this method will check
     * to see if the probability of mutation is within the given parameter and
     * if so will mutate the child.
     * 
     * @param children
     *            list of potential children individuals to be mutated according
     *            to the mutation probability
     */
    private void mutate(List<Individual> children)
    {
        // mutate each new child based on mutation rate
        for (int j = 0; j < children.size(); j++)
        {
            if (Math.random() < parameters.getMutationRate())
            {
                int type = (int) (Math.random() * 3);
                int index = (int) (Math.random() * children.get(j).getSize());

                if (children.get(j).getSize() == 1 && type == 0)
                    type = 1;

                // apply appropriate mutation
                Allele newAllele = null;

                // if type is 1, mutation is insertion of a
                // new allele necessitating generation of a new one

                List<List<Refactoring>> availableSequences = new ArrayList<List<Refactoring>>();
                availableSequences.addAll(sequences);
                Individual child = children.get(j);
                for (int i = 0; i < child.getSize(); i++)
                {
                    availableSequences.remove(child.getAllele(i).getRefactoringSequence());
                }

                if (type == 1)
                    newAllele = newAllele(availableSequences);

                // if type is 2, mutation is modification of an
                // existing allele
                else if (type == 2)
                {
                    Allele temp = children.get(j).getAllele(index);
                    availableSequences.add(temp.getRefactoringSequence());

                    newAllele = newAllele(availableSequences);
                }

                children.get(j).mutate(type, index, newAllele);
            }
        }
    }

    /**
     * Generates the initial population to start the genetic algorithm.
     * 
     * @param size
     *            The size of the initial population to be generated
     * @return List of individuals representing the initial population.
     */
    private List<Individual> initialPopulation(int size)
    {
        List<Individual> population = new ArrayList<Individual>();

        for (int i = 0; i < size; i++)
        {
            population.add(newIndividual());
        }

        return population;
    }

    /**
     * Method that contains the actual Genetic Algorithm controlling the
     * refactoring.
     */
    public CodeGraph runGP()
    {
        List<Individual> population = initialPopulation(parameters.getPopSize());

        int generation = 0;
        calcFitnessAll(population, generation);
        Individual best = findBest(population, generation);
        double smell = calcSmell(applyIndividual(best), generation, best);
        controller.recordSmellLog(generation, best.getTotalSmell(), best.getSmells().getIndividualVals());
        controller.recordFitnessLog(generation, best.getTotalFitness(), best.getFitness().getIndividualVals());

        do
        {
            generation++;
            List<Individual> newGeneration = new Vector<Individual>();
            newGeneration.addAll(population);

            // fitness proportional selection, crossover, and mutation
            newGeneration.addAll(createChildren(population));
            calcFitnessAll(newGeneration, generation);

            // fitness proportional retention without replacement
            // and force keeping of single best individual
            retainPopulation(generation, population, newGeneration);

            best = findBest(population, generation);
            controller.recordFitnessLog(generation, best.getTotalFitness(), best.getFitness().getIndividualVals());
            controller.recordSmellLog(generation, best.getTotalSmell(), best.getSmells().getIndividualVals());

            if (generation % parameters.getMaxLogLength() == 0 && generation > 0)
            {
                controller.purgeLog();
            }
        }
        while (generation < parameters.getMaxIterations() || smell < (parameters.getSmellFactor() * initialSmell));

        Individual bestIndividual = findBest(population, generation);

        StringBuilder sb = new StringBuilder();
        sb.append("\n\n");
        sb.append("Best Found: ");
        sb.append(bestIndividual);
        sb.append("\n");
        controller.recordHeading(generation, sb.toString());

        CodeGraph bestGraph = applyIndividual(bestIndividual);

        displayFitnessHeader(generation);
        calcFitness(generation, bestGraph, bestIndividual);
        controller.recordSmellLog(generation, bestIndividual.getTotalSmell(), bestIndividual.getSmells()
                .getIndividualVals());
        controller.recordFitnessLog(generation, bestIndividual.getTotalFitness(), bestIndividual.getFitness()
                .getIndividualVals());

        return bestGraph;
    }

    /*
     * (non-Javadoc)
     * @see java.lang.Runnable#run()
     */
    public void run()
    {
        CodeGraph bestGraph = runGP();
        controller.finish(bestGraph);
    }

    /**
     * Calculates the fitness for all members of a supplied list of individuals
     * representing an entire population or portion of a population used by the
     * genetic algorithm.
     * 
     * @param population
     *            List of individuals who require fitness calculations.
     * @param generation
     *            The generation of the genertic algorithm to which this
     *            population belongs.
     */
    private void calcFitnessAll(List<Individual> population, int generation)
    {
        controller.recordHeading(generation, "Measurements");
        displayFitnessHeader(generation);

        for (Individual ind : population)
        {
            calcFitness(generation, applyIndividual(ind), ind);
            calcSmell(applyIndividual(ind), generation, ind);
        }
    }

    /**
     * Finds the Best Individual (by fitness) of a population and returns this
     * individual.
     * 
     * @param population
     *            List of individuals within which to search for the best
     *            individual
     * @param generation
     *            generation of the genetic algorithm for which the best
     *            individual is to be found for
     * @return Best Individual as measure by fitness, where the returned
     *         individual has the highest fitness of all the population. If
     *         multiple individuals exist with the highest fitness, the first
     *         one found is returned.
     */
    private Individual findBest(List<Individual> population, int generation)
    {
        List<Double> fitVals = new Vector<Double>();

        for (int i = 0; i < population.size(); i++)
        {
            Individual ind = population.get(i);
            fitVals.add(ind.getTotalFitness() + ind.getTotalSmell());
        }

        double value = Collections.min(fitVals);
        controller.recordBestTotalFitness(generation, population.get(fitVals.indexOf(value)).getTotalFitness());

        return population.get(fitVals.indexOf(value));
    }

    /**
     * Calculates the overall fitness of the provided graph, assuming that this
     * graph has had a set of refactorings applied.
     * 
     * @param generation
     *            The current generation to which the individual, represented by
     *            the graph and for which fitness is to be calculated, belongs
     *            to
     * @param graph
     *            the refactored graph
     * @param ind
     *            The individual for which the fitness values are to be stored
     * @return the fitness value for the set of applied reactorings.
     */
    public double calcFitness(int generation, CodeGraph graph, Individual ind)
    {
        double fitness = 0;

        boolean isFirst = true;
        int i = 0;
        for (Metric m : controller.getMetrics())
        {
            double tempM = m.measure(graph);
            controller.recordIndividualFitnessMetric(generation, m.getName(), tempM, isFirst);

            if (ind != null)
                ind.addFitnessValue(tempM);
            else
                initialVals.addIndividualVal(tempM);

            fitness += tempM;
            isFirst = false;

            i++;
        }

        if (ind == null)
            initialVal = fitness;

        controller.recordIndividualFitnessMetric(generation, "Total", fitness, false);
        return fitness;
    }

    /**
     * Given an individual composing a set of refactorings to be applied. This
     * method iteratively applies the refactorings in the order specified by the
     * list and generates a new graph representing the applied refactorings.
     * 
     * @param individual
     *            The set of refactorings to be applied to the Graph
     */
    public CodeGraph applyIndividual(Individual individual)
    {
        CodeGraph clone = GraphPool.getInstance().acquireCodeGraph();

        List<Allele> chromosome = individual.getChromosome();

        for (Allele allele : chromosome)
        {
            // apply refactorings given by the individual
            for (Refactoring ref : allele.getRefactoringSequence())
                ref.execute(clone);
        }
        return clone;
    }

    /**
     * Calculates the overall Code Smell of the provided CodeGraph
     * 
     * @param graph
     *            CodeGraph over which code smell is to be measured
     * @param generation
     *            Generation for which the codesmell values are being calculated
     *            and to which the provided individual belongs.
     * @param individual
     *            TODO
     * @return total codesmell value for the given codegraph
     */
    public double calcSmell(CodeGraph graph, int generation, Individual individual)
    {
        double smellValue = 0;

        boolean isFirst = true;
        int i = 0;
        List<CodeSmell> smells = controller.getSmells();
        for (CodeSmell smell : smells)
        {
            double value = 0;

            if (generation >= 0)
            {
                value = smell.measure(graph);
                individual.addSmellValue(value);
            }
            else
            {
                value = smell.initialMeasurement(graph, sequences);
                initialSmells.addIndividualVal(value);
            }
            controller.recordIndividualSmell(smell.getName(), value, isFirst);
            smellValue += value;
            isFirst = false;

            i++;
        }

        controller.recordTotalSmell(smellValue);
        return smellValue;
    }

    /**
     * For the given generation, this method logs the header for the displayed
     * log in the UI
     * 
     * @param generation
     *            current generation of the GA
     */
    private void displayFitnessHeader(int generation)
    {
        StringBuilder sb = new StringBuilder();
        for (Metric m : controller.getMetrics())
            sb.append(String.format("%10s,", m.getShortName()));

        sb.append(String.format("%10s", "Total"));

        List<CodeSmell> smells = controller.getSmells();

        for (CodeSmell smell : smells)
        {
            sb.append(String.format("%10s,", smell.getShortName()));
        }

        controller.recordCodeSmellHeading(generation, sb.toString() + String.format("%10s", "Total"));
    }
}
